Sia \(L\) un insieme di lettere proposizionali.
Definizione Un’interpretazione è una funzione \(i \colon L \longrightarrow \{ 0 , 1 \}\).
L’idea è che un’interpretazione \(i\) assegna valori di verità (\(0\) per falso, \(1\) per vero) alle lettere proposizionali scelte.
Esempio
Sia \(L = \{ \mathrm{A}, \mathrm{B} \}\). Allora l’interpretazione \(i \colon L \to \{ 0,1 \}\) definita da \[\begin{aligned} i(\mathrm{A}) & = 0 \\ i(\mathrm{B}) & = 1\end{aligned}\] “descrive” la situazione in cui \(\mathrm{A}\) è falsa e \(\mathrm{B}\) è vera.
L’interpretazione \(i(\mathrm{A}) = i(\mathrm{B}) = 1\) “descrive” invece la situazione in cui sia \(\mathrm{A}\) che \(\mathrm{B}\) sono vere.
Valutazioni
Definizione Una valutazione è una funzione \(v \colon Prop ( L ) \to \{0, 1\}\) che soddisfa le seguenti condizioni:
| \[v ( ( \neg \mathrm{P} ) )\] | \[=\] | \[1 - v ( \mathrm{P} ) \] |
|---|---|---|
| \[v ( ( \mathrm{P} \wedge \mathrm{Q} ) )\] | \[=\] | \[\min \{v( \mathrm{P} ) , v ( \mathrm{Q} ) \} \] |
| \[v ( ( \mathrm{P} \vee \mathrm{Q} ) )\] | \[=\] | \[\max\{ v ( \mathrm{P} ) , v ( \mathrm{Q} )\] |
| \[v ( ( \mathrm{P} \rightarrow \mathrm{Q} ) )\] | \[=\] | \[\max \{1 - v ( \mathrm{P} ), v ( \mathrm{Q} )\] |
| \[v ( ( \mathrm{P} \leftrightarrow \mathrm{Q} ) )\] | \[=\] | \[1 - | v ( \mathrm{P} ) - v ( \mathrm{Q} )|\] |
Dunque una valutazione assegna valori di verità a tutte le (infinite!) proposizioni che si possono scrivere a partire da \(L\). Le condizioni nella definizione di valutazione sono essenzialmente espressioni analitiche (in termini di funzioni) delle tavole di verità dei connettivi.
Esempio
La condizione \[v ( ( \neg \mathrm{P} ) ) = 1 - v ( \mathrm{P} )\] fa sì che
se \(v(\mathrm{P}) = 0\) (ovvero “\(\mathrm{P}\) è falsa”), allora \(v ( ( \neg \mathrm{P} ) ) = 1-0 = 1\) (ovvero “\((\neg \mathrm{P})\) è vera”);
se \(v(\mathrm{P}) = 1\) (ovvero “\(\mathrm{P}\) è vera”), allora \(v ( ( \neg \mathrm{P} ) ) = 1-1 = 0\) (ovvero “\((\neg \mathrm{P})\) è falsa”).
Questo descrive esattamente la tavola di verità della negazione:
| \[ \mathrm{P}\] | \[\neg \mathrm{P} \] |
|---|---|
| \[F\] | \[V\] |
| \[V\] | \[F\] |
ovvero:
| \[ \mathrm{P}\] | \[\neg \mathrm{P} \] |
|---|---|
| \[0\] | \[1\] |
| \[0\] | \[1\] |
Se \(v(\mathrm{P}) = v(\mathrm{Q}) = 0\) (“\(\mathrm{P}\) e \(\mathrm{Q}\) sono false”), allora \(v ( ( \mathrm{P} \wedge \mathrm{Q} ) ) = \min \{ 0,0 \} = 0\) (“\((\mathrm{P} \wedge \mathrm{Q})\) è falsa”).
Se \(v(\mathrm{P}) =1\) e \(v(\mathrm{Q}) = 0\) (“\(\mathrm{P}\) è vera e \(\mathrm{Q}\) è falsa”), allora \(v ( ( \mathrm{P} \wedge \mathrm{Q} ) ) = \min \{ 1,0 \} = 0\) (“\((\mathrm{P} \wedge \mathrm{Q})\) è falsa”).
Se \(v(\mathrm{P}) =0\) e \(v(\mathrm{Q}) = 1\) (“\(\mathrm{P}\) è falsa e \(\mathrm{Q}\) è vera”), allora \(v ( ( \mathrm{P} \wedge \mathrm{Q} ) ) = \min \{ 0,1 \} = 0\) (“\((\mathrm{P} \wedge \mathrm{Q})\) è falsa”).
Se \(v(\mathrm{P}) = v(\mathrm{Q}) = 1\) (“\(\mathrm{P}\) e \(\mathrm{Q}\) sono vere”), allora \(v ( ( \mathrm{P} \wedge \mathrm{Q} ) ) = \min \{ 1,1 \} = 1\) (“\((\mathrm{P} \wedge \mathrm{Q})\) è vera”).
Questo descrive esattamente la tavola di verità della congiunzione:
| \[\mathrm{P}\] | \[\mathrm{Q}\] | \[\mathrm{P} \wedge \mathrm{Q} \] |
|---|---|---|
| \[F\] | \[F\] | \[F\] |
| \[V\] | \[F\] | \[V\] |
| \[V\] | \[F\] | \[F\] |
| \[V\] | \[V\] | \[V\] |
ovvero:
| \[\mathrm{P}\] | \[\mathrm{Q}\] | \[\mathrm{P} \wedge \mathrm{Q} \] |
|---|---|---|
| \[0\] | \[0\] | \[0\] |
| \[1\] | \[0\] | \[1\] |
| \[1\] | \[0\] | \[0\] |
| \[1\] | \[1\] | \[1\] |
Esercizio Verificare che le rimanenti condizioni nella definizione di valutazione descrivono le tavole di verità dei rispettivi connettivi.
Ogni valutazione \(v \colon Prop(L) \to \{ 0,1\}\) fornisce, in particolare, una corrispondente interpretazione \(i \colon L \to \{ 0,1\}\) che si ottiene stabilendo che per ogni \(\mathrm{A} \in L\) \[i(\mathrm{A}) \stackrel{\text{\tiny\rm def}}{=}v((\mathrm{A})).\]
In altre parole, \(i\) è la “restrizione” di \(v\) ad \(L\) una volta che si identifichi ciascuna lettera proposizionale \(\mathrm{A}\) con la corrispondente formula atomica \((\mathrm{A})\): per questa ragione la denoteremo con \(v \restriction L\).
Vediamo ora che, viceversa, da un’interpretazione \(i\) si può ottenere in maniera canonica una valutazione, che denoteremo con \(i^*\).
Ogni interpretazione \(i\) si estende a una valutazione \(i^{\ast}\) ponendo \(i^{\ast}( ( \mathrm{A} ) ) = i ( \mathrm{A} )\) per ogni \(\mathrm{A} \in L\), e definendo \(i^{\ast} ( P )\) per le proposizioni \(P\) non atomiche così:
| \[i^{\ast} ( ( \neg \mathrm{P} ) )\] | \[=\] | \[1 - i^{\ast} ( \mathrm{P} )\] |
|---|---|---|
| \[i^{\ast} ( ( \mathrm{P} \wedge \mathrm{Q} ) )\] | \[=\] | \[\min \{ i^{\ast}( \mathrm{P} ) , i^{\ast} ( \mathrm{Q} )\}\] |
| \[i^{\ast} ( ( \mathrm{P} \vee \mathrm{Q} ) )\] | \[=\] | \[\max\{ i^{\ast} ( \mathrm{P} ) , i^{\ast} ( \mathrm{Q} ) \} \] |
| \[i^{\ast} ( ( \mathrm{P} \rightarrow \mathrm{Q} ) )\] | \[=\] | \[ \max \{1 - i^{\ast} ( \mathrm{P} ), i^{\ast} ( \mathrm{Q} ) \} \] |
| \[i^{\ast} ( ( \mathrm{P} \leftrightarrow \mathrm{Q} ) )\] | \[=\] | \[1 - | i^{\ast} ( \mathrm{P} ) - i^{\ast} ( \mathrm{Q} )|\] |
Le condizioni sono le stesse della definizione di valutazione, ovvero “descrivono” la tavola di verità dei connettivi corrispondenti!
Osservazione L’interpretazione \(v \restriction L\) indotta da una valutazione \(v\) è tale che \((v \restriction L)^* = v\). Viceversa, per ogni interpretazione \(i\) si ha che \(i^* \restriction L = i\).
Come si calcola \(i^*\)? Data un’interpretazione \(i\) ed una proposizione non atomica \(\mathrm{P} \in Prop(L)\), per calcolare \(i^*(\mathrm{P})\) bisognerà prima di tutto aver calcolato il valore di \(i^*\) sulle sottoproposizioni principali di \(\mathrm{P}\). Ripetendo questo ragionamento anche per le sottoproposizioni (principali) di \(\mathrm{P}\), si vede che per calcolare \(i^*(\mathrm{P})\) bisognerà prima calcolare \(i^*\) su tutte le sue sottoproposizioni, partendo da quelle atomiche e seguendo poi la struttura dell’albero sintattico.
Osservazione Il valore di \(i^*(\mathrm{P})\) dipende solo dal valore assunto da \(i\) sulle lettere proposizionali che occorrono in \(\mathrm{P}\).
Esempio. Sia \(L = \{ \mathrm{A}, \mathrm{B}, \mathrm{C}, \mathrm{D} \}\) e \(\mathrm{P} \in Prop(L)\) la proposizione \((\mathrm{A} \wedge \neg \mathrm{B}) \to \neg \mathrm{D}\). Un’interpretazione \(i \colon L \to \{ 0,1 \}\) si ottiene assegnando un valore di verità a tutte le lettere proposizionali di \(L\). Tuttavia, solo i valori \(i(\mathrm{A})\), \(i(\mathrm{B})\) e \(i(\mathrm{D})\) sono rilevanti per il calcolo di \(i^*(\mathrm{P})\), mentre il valore \(i(\mathrm{C})\) è del tutto irrilevante per questo scopo.
Un esempio Sia \(i(\mathrm{A}) = 1\) e \(i(\mathrm{B}) = 0\). Calcoliamo \(i^*(\mathrm{P})\) dove \(\mathrm{P}\) è \((\mathrm{A} \wedge \neg \mathrm{B}) \vee \neg \mathrm{A}\). L’albero sintattico di \(\mathrm{P}\) è Didascalia figura:Poichè \(\mathrm{P}\) è della forma \(\mathrm{R} \vee \mathrm{S}\), dovremo innanzitutto calcolare \(i^*(\mathrm{R})\) e \(i^*(\mathrm{S})\) per poter poi calcolare \(i^*(\mathrm{P}) = \max \{ i^*(\mathrm{R}), i^*(\mathrm{S}) \}\).
A sua volta, poichè \(\mathrm{R}\) è della forma \(\mathrm{W} \wedge \mathrm{T}\), dovremo prima calcolare \(i^*(\mathrm{W})\) e \(i^*(\mathrm{T})\) per poter poi calcolare \(i^*(\mathrm{R}) = \min \{ i^*(\mathrm{W}), i^*(\mathrm{T}) \}\). E così via fino alle foglie, in cui il valore di \(i^*\) è dato esplicitamente da \(i\).
Un esempio (continua) Dunque per calcolare \(i^*( (\mathrm{A} \wedge \neg \mathrm{B}) \vee \neg \mathrm{A})\) a partire da \(i(\mathrm{A}) = 1\) e \(i(\mathrm{B}) = 0\) procederemo come segue Didascalia figura:Si ricordi che per definizione \(i^*(\mathrm{A}) = i(\mathrm{A}) = 1\) e \(i^*(\mathrm{B}) = i(\mathrm{B}) = 0\).
| \[i^*(\neg \mathrm{B})\] | \[=\] | \[1 - i^*(\mathrm{B})\] | \[=\] | \[ 1 - 0 = 1\] |
|---|---|---|---|---|
| \[i^*(\mathrm{A} \wedge \neg \mathrm{B})\] | \[=\] | \[\min \{ i^*(\mathrm{A}), i^*(\neg \mathrm{B}) \}\] | \[=\] | \[\min \{ 1 , 1 \} = 1\] |
| \[i^*(\neg \mathrm{A})\] | \[=\] | \[1 - i^*(\mathrm{A})\] | \[=\] | \[1-1 = 0\] |
| \[i^*( (\mathrm{A} \wedge \neg \mathrm{B}) \vee \neg \mathrm{A})\] | \[=\] | \[\max \{ i^*(\mathrm{A} \wedge \neg \mathrm{B}) , i^*(\neg \mathrm{A}) \} \] | \[=\] | \[\max \{ 1,0 \} = 1\] |
Un esempio (continua)
Dunque per determinare \(i^*( (\mathrm{A} \wedge \neg \mathrm{B}) \vee \neg \mathrm{A})\) a partire da \(i(\mathrm{A}) = 1\) e \(i(\mathrm{B}) = 0\) abbiamo calcolato in successione i valori seguenti:
| \[i^*(\neg \mathrm{B})\] | \[=\] | \[1 - i^*(\mathrm{B})\] | \[=\] | \[ 1 - 0 = 1\] |
|---|---|---|---|---|
| \[i^*(\mathrm{A} \wedge \neg \mathrm{B})\] | \[=\] | \[\min \{ i^*(\mathrm{A}), i^*(\neg \mathrm{B}) \}\] | \[=\] | \[\min \{ 1 , 1 \} = 1\] |
| \[i^*(\neg \mathrm{A})\] | \[=\] | \[1 - i^*(\mathrm{A})\] | \[=\] | \[1-1 = 0\] |
| \[i^*( (\mathrm{A} \wedge \neg \mathrm{B}) \vee \neg \mathrm{A})\] | \[=\] | \[\max \{ i^*(\mathrm{A} \wedge \neg \mathrm{B}) , i^*(\neg \mathrm{A}) \} \] | \[=\] | \[\max \{ 1,0 \} = 1\] |
Graficamente possiamo rappresentare questi conti ponendo i valori così ottenuti sotto la proposizione corrispondente:
| \[\mathrm{A}\] | \[\mathrm{B}\] | \[\neg \mathrm{B}\] | \[\mathrm{A} \wedge \neg \mathrm{B}\] | \[\neg \mathrm{A}\] | \[(\mathrm{A} \wedge \neg \mathrm{B}) \vee \neg \mathrm{A}\] |
|---|---|---|---|---|---|
| \[1\] | \[0\] | \[1\] | \[1\] | \[0\] | \[1\] |
Dunque calcolare \(i^*(\mathrm{P})\) corrisponde a calcolare una riga della tavola di verità di \(\mathrm{P}\) — la riga determinata dall’interpretazione \(i\).
Per calcolare una tavola di verità di una proposizione \(\mathrm{P}\) bisogna quindi:
costruire l’albero sintattico di \(\mathrm{P}\), che ci permetterà di
verificare che \(\mathrm{P}\) è una proposizione ben formata;
determinare le sottoproposizioni di \(\mathrm{P}\) e l’ordine con cui andranno considerate;
individuare un linguaggio \(L\) “minimale” tale che \(\mathrm{P} \in Prop(L)\): infatti \(L\) è costituito da tutte le (lettere proposizionali che formano le) sottoproposizioni atomiche di \(\mathrm{P}\), che a loro volta corrispondono alle foglie dell’albero;
considerare tutte le possibili interpretazioni \(i \colon L \to \{ 0,1 \}\), ovvero tutte le possibili combinazioni di assegnazioni di valori di verità alle lettere proposizionali in \(L\) (ciascuna interpretazione \(i\) sarà una diversa riga nella tavola di verità);
estendere ciascuna di tali interpretazioni \(i\) alla corrispondente valutazione \(i^*\) fino a calcolare \(i^*(\mathrm{P})\).
Sia \(\mathrm{P}\) la proposizione \(\neg \mathrm{A} \vee (\mathrm{B} \to \mathrm{A})\).
Step 1. Costruire l’albero sintattico di \(\neg \mathrm{A} \vee (\mathrm{B} \to \mathrm{A})\), che ci permetterà di determinare le sue sottoproposizioni e l’ordine con cui andranno considerate, ed un opportuno linguaggio \(L\).
Didascalia figura:
| \[\mathrm{A}\] | \[\mathrm{B}\] | \[\neg \mathrm{A}\] | \[\mathrm{B} \to \mathrm{A}\] | \[\neg \mathrm{A} \vee (\mathrm{B} \to \mathrm{A})\] |
|---|---|---|---|---|
| \[\] | \[\] | \[\] | \[\] | \[\] |
| \[\] | \[\] | \[\] | \[\] | \[\] |
| \[\] | \[\] | \[\] | \[\] | \[\] |
| \[\] | \[\] | \[\] | \[\] | \[\] |
Sia \(\mathrm{P}\) la proposizione \(\neg \mathrm{A} \vee (\mathrm{B} \to \mathrm{A})\).
Step 2. Considerare tutte le possibili interpretazioni \(i \colon L \to \{ 0,1 \}\).
Didascalia figura:
| \[\mathrm{A}\] | \[\mathrm{B}\] | \[\neg \mathrm{A}\] | \[\mathrm{B} \to \mathrm{A}\] | \[\neg \mathrm{A} \vee (\mathrm{B} \to \mathrm{A})\] |
|---|---|---|---|---|
| \[0\] | \[0\] | \[\] | \[\] | \[\] |
| \[0\] | \[1\] | \[\] | \[\] | \[\] |
| \[1\] | \[0\] | \[\] | \[\] | \[\] |
| \[1\] | \[1\] | \[\] | \[\] | \[\] |
Sia \(\mathrm{P}\) la proposizione \(\neg \mathrm{A} \vee (\mathrm{B} \to \mathrm{A})\).
Step 3. Estendere ciascuna di tali interpretazioni \(i\) alla corrispondente valutazione \(i^*\) fino a calcolare \(i^*(\mathrm{P})\).
Didascalia figura:
| \[\mathrm{A}\] | \[\mathrm{B}\] | \[\neg \mathrm{A}\] | \[\mathrm{B} \to \mathrm{A}\] | \[\neg \mathrm{A} \vee (\mathrm{B} \to \mathrm{A})\] |
|---|---|---|---|---|
| \[0\] | \[0\] | \[1\] | \[1\] | \[1\] |
| \[0\] | \[1\] | \[1\] | \[0\] | \[1\] |
| \[1\] | \[0\] | \[0\] | \[1\] | \[1\] |
| \[1\] | \[1\] | \[0\] | \[1\] | \[1\] |
Alcune nozioni logiche
Se \(i^{\ast}(\mathrm{P}) = 1\), si dice che \(\mathrm{P}\) è vera nell’interpretazione \(i\), o che \(i\) soddisfa \(\mathrm{P}\), o che \(i\) è un modello di \(\mathrm{P}\), e si scrive anche \[i \models \mathrm{P}.\]
Se esiste almeno un’interpretazione \(i\) tale che \(i \models \mathrm{P}\), si dice che \(\mathrm{P}\) è soddisfacibile, o coerente.
Se non esiste alcun modello di \(\mathrm{P}\), si dice che \(\mathrm{P}\) è insoddisfacibile, o incoerente, o contraddittoria, o una contraddizione.
Se per ogni interpretazione \(i\) si ha \(i \models \mathrm{P}\), si dice che \(\mathrm{P}\) è (logicamente) valida, o logicamente vera, o una tautologia, e si scrive \[\models \mathrm{P} .\]
Le nozioni appena viste si possono anche estendere ad insiemi di proposizioni.
Sia \(\Gamma \subseteq Prop(L)\) un insieme (finito o infinito) di proposizioni costruite a partire dallo stesso insieme di lettere proposizionali \(L\).
Un’interpretazione \(i \colon L \to \{ 0,1 \}\) è un modello di \(\Gamma\), in simboli \[i \models \Gamma,\] se \(i \models \mathrm{P}\) per ogni \(\mathrm{P} \in \Gamma\). In questo caso diciamo anche che \(\Gamma\) è soddisfatto da \(i\), o che \(i\) soddisfa \(\Gamma\).
\(\Gamma\) si dice soddisfacibile (o coerente) se esiste un’interpretazione \(i\) tale che \(i \models \Gamma\); in caso contrario, ovvero se \(i \not\models \Gamma\) per ogni interpretazione \(i\), si dice che \(\Gamma\) è insoddisfacibile (o incoerente).
L’insieme di proposizioni \(\Gamma\) è valido se \(i \models \Gamma\) per ogni interpretazione \(i\). In questo caso scriviamo \(\models \Gamma\).
Osservazioni Sia \(\Gamma \subseteq Prop(L)\).
\(\Gamma\) è valido se e solo se ogni \(\mathrm{P} \in \Gamma\) è una tautologia.
è invece possibile che tutte le proposizioni \(\mathrm{P} \in \Gamma\) siano soddisfacibili, ma che \(\Gamma\) non sia soddisfacibile come insieme di proposizioni (si consideri ad esempio \(\Gamma = \{ \mathrm{A}, \neg \mathrm{A} \}\)).
Se \(\Gamma = \{ \mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \}\) è un insieme finito, allora per ogni interpretazione \(i\)
\(i \models \Gamma\) se e solo se \(i \models \mathrm{P}_{1}\wedge \dotsc \wedge \mathrm{P}_{n}.\)
Di conseguenza, \(\Gamma\) è soddisfacibile/insoddisfacibile/valido se e solo se la proposizione \(\mathrm{P}_{1} \wedge \dotsc \wedge \mathrm{P}_{n}\) è soddisfacibile/insoddisfacibile/valida.